import java.util.List;

public class ReplaceWords {

    public String replaceWords(List<String> dictionary, String sentence) {
        PrefixTree prefixTree = new PrefixTree();
        for (int i = 0; i < dictionary.size(); i++) {
            prefixTree.add(dictionary.get(i));
        }
        String[] words = sentence.split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(prefixTree.search(words[0]));
        for (int i = 1; i < words.length; i++) {
            stringBuilder.append(" ");
            stringBuilder.append(prefixTree.search(words[i]));
        }
        return stringBuilder.toString();
    }
}

class PrefixTree {
    PrefixTree[] next;
    int end;
    public PrefixTree() {
        next = new PrefixTree[26];
    }

    public void add(String s) {
        char[] chars = s.toCharArray();
        PrefixTree node = this;
        for (int i = 0; i < chars.length; i++) {
            if (node.next[chars[i] - 'a'] == null) {
                node.next[chars[i] - 'a'] = new PrefixTree();
            }
            node = node.next[chars[i] - 'a'];
        }
        node.end++;
    }

    public String search(String s) {
        char[] chars = s.toCharArray();
        PrefixTree node = this;
        for (int i = 0; i < chars.length; i++) {
            if (node.next[chars[i] - 'a'] == null) return s;
            if (node.next[chars[i] - 'a'].end != 0) return s.substring(0, i + 1);
            node = node.next[chars[i] - 'a'];
        }
        return s;
    }
}
